package demo;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //圆中最长的环
    public int longestCycle(int[] edges) {
        int n = edges.length;
        boolean[] visited = new boolean[n];
        int res = -1;

        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;

            // 用 HashMap 记录节点在路径中的位置（索引）
            Map<Integer, Integer> path = new HashMap<>();
            int curr = i;
            int pos = 0; // 当前路径的长度

            while (curr != -1) {
                if (path.containsKey(curr)) {
                    // 发现环，计算环的长度
                    res = Math.max(res, pos - path.get(curr));
                    break;
                }
                if (visited[curr]) break; // 已访问过但不在当前路径中

                visited[curr] = true;
                path.put(curr, pos);
                pos++;
                curr = edges[curr];
            }
        }
        return res;
    }

    //稀疏数组搜索
    public int findString(String[] words, String s) {
        //二分
        int len=words.length;
        int i=0;
        int j=len-1;
        int mid=(j-i)/2+i;
        while(i<=j){
            //index的作用{当words[mid]为“”空字符是，我们记录mid的位置，那么我们就可以大胆的对mid进行移位操作了，无论是左移还是右移，目的就是为了找到一个非空字符串跟s来比较，大了往左，小了往右}
            //还是一道简单的二分查找问题，就是多了一个干扰项“”，和字符串的比较大小words[mid].compareTo(s)>0
            //index的作用就体现了，当你一开始就对mid移动，那么我去有区间的路上要把我最开始走过的连续空字符的道路给去掉
            int index=mid;
            while(mid>i &&words[mid].equals(""))mid--;
            if(words[mid].equals(s))return mid;
            else if(words[mid].compareTo(s)>0){
                j=mid-1;
            }else {
                i=index+1;
            }
            mid=(j-i)/2+i;
        }
        return -1;
    }
}
